#include<bits/stdc++.h>
using namespace std;
const int N=100000+10;
const int M=500000+10;
vector<int>edge[N],adge[N];
int p[N];
bool vis[10][N];
queue<int>q;
void bfs(int x,int key)
{
	while(!q.empty())
	q.pop();
	q.push(x);
	vis[key][x]=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		if(key==1)
		{
			for(int i=0;i<edge[u].size();i++)
			{
				int v=edge[u][i];
				if(vis[key][v])continue;
				vis[key][v]=true;
				q.push(v);
			}			
		}
		else if(key==2)
		{
			for(int i=0;i<adge[u].size();i++)
			{
				int v=adge[u][i];
				if(vis[key][v])continue;
				vis[key][v]=true;
				q.push(v);
			}		
		}
	}
}
int mx;
void solve(int x,int key)
{
	while(!q.empty()) q.pop();
	q.push(x);
	vis[key][x]=true;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=0;i<edge[u].size();i++)
		{
			int v=edge[u][i];
			if(vis[key][v])continue;
			if(vis[2][v])
			mx=max(mx,p[v]-p[x]);
			
			vis[key][v]=true;
			q.push(v);
		}
	}
}
int a[N];
bool cmp(int a1,int a2)
{
	return p[a1]<p[a2];
}
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		a[i]=i;
	}
	for(int i=1;i<=n;i++)
	edge[i].clear(),adge[i].clear();
	while(m--)
	{
		int u,v,k;
		scanf("%d%d%d",&u,&v,&k);
		edge[u].push_back(v);
		adge[v].push_back(u);
		if(k==2)
		{
			edge[v].push_back(u);
			adge[u].push_back(v);
		}
	}
	memset(vis,0,sizeof(vis));
	//跑顶点1能到达的所有节点，并标记 
	bfs(1,1);
	//跑能到达顶点n的所有节点，并标记 
	bfs(n,2);
	//按价格从小到大排序 
	sort(a+1,a+n+1,cmp);
	mx=0;
	//开始做一遍BFS处理 
	for(int i=1;i<=n;i++)
	{
		//vis[3]表示在这次的bfs中被处理过的点，可以不再遍历了 
		if(vis[1][a[i]]&&vis[3][a[i]]==false)
		{
			solve(a[i],3);
		}
	}
	cout<<mx<<endl;
	return 0;
}